#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

const size_t NumQueues = 8;
size_t cnt = 0;

void print_soln(const vector<size_t>& cols);
bool check(const vector<size_t>& cols);
void permute(vector<size_t>& cols, size_t pos);

void solve_eight_queue() {
  vector<size_t> cols(NumQueues, 0);
  for (size_t i = 0; i < NumQueues; i++) 
    cols[i] = i;

  permute(cols, 0);
  cout << "soln #: " << cnt << endl;
}

void permute(vector<size_t>& cols, size_t pos) {
  if (pos == cols.size() && check(cols)) {
    print_soln(cols);
    cnt++;
  }

  for (size_t i = pos; i < cols.size(); i++) {
    swap(cols[pos], cols[i]);
    permute(cols, pos+1);
    swap(cols[pos], cols[i]);
  }
}

bool check(const vector<size_t>& cols) {
  for (size_t i = 0; i < cols.size(); i++) {
    for (size_t j = i+1; j < cols.size(); j++) {
      if (i+cols[i] == j+cols[j]) {
	return false;
      }
      if ((int) i - (int) cols[i] == (int) j - (int) cols[j]) {
	return false;
      }
    }
  }
  return true;
}

void print_soln(const vector<size_t>& cols) {
  cout << endl << endl;
  size_t len = cols.size();
  for (size_t r = 0; r < len; r++) {
    for (size_t c = 0; c < len; c++) {
      if (c == cols[r]) 
	cout << "+" << " ";
      else
	cout << "*" << " ";
    }
    cout << endl;
  }
}

int main() {
  cout << "Solutions to eight queues" << endl;
  solve_eight_queue();
  return 0;
}
